//
// Created by Bianwy on 2024/2/10.
//
#include <iostream>
#include <stack>

using namespace std;
// 二叉链表中结点类型
struct BTNode
{
    char data;  // 数据元素
    BTNode* lchild; // 指向左孩子结点
    BTNode* rchild; // 指向右孩子结点
    // 构造函数
    BTNode():lchild(nullptr),rchild(nullptr){}
    BTNode(char d):data(d),lchild(nullptr),rchild(nullptr) { }  // 注意构造函数的写法
};
// 二叉树类
class BTree
{
public:
    BTNode* r;  // 二叉树的根结点r
    BTree():r(nullptr) {}
    ~BTree()    // 析构函数
    {
        DestroyBTree(r);    // 调用DestroyBTree()函数
        r = nullptr;           // 置为空树
    }
    //==========二叉树的基本运算============
public:
    // 创建以r为根结点的二叉链存储结构
    void CreateBTree(string str)
    {
        stack<BTNode*> st;  // 定义一个栈st
        BTNode* p;  // 指向前面刚创建的p结点
        bool flag;  // 指示处理的是左孩子还是右孩子
        int i = 0;
        while (i < str.length())    // 循环扫描str中每个字符
        {
            switch (str[i])
            {
                case '(':
                    st.push(p); // 刚刚新建的结点有左孩子，将其进栈
                    flag = true;
                    break;
                case ')':
                    st.pop();   // 栈顶结点的子树处理完，出栈
                    break;
                case ',':
                    flag = false;   // 开始处理栈顶结点的右孩子
                    break;
                default:
                    p = new BTNode(str[i]); // 新建一个结点p
                    if(r == nullptr)    // 尚未建立根节点
                        r = p;          // p作为根节点
                    else            // 已建立二叉树根节点
                    {
                          if(flag && !st.empty())   // 新结点p作为栈顶结点的左孩子
                              st.top()->lchild = p;
                          else if(!st.empty())      // 新结点p作为栈顶结点的右孩子
                              st.top()->rchild = p;
                    }
                    break;
            }
            i++;    // 继续遍历
        }
    }
    // 将二叉链转换成括号表示法并输出
    void DispBTree()
    {
        DispBTree(r);
    }
private:
    void DispBTree(BTNode* b)   // 被DispBTree函数调用
    {
        if(b != nullptr)
        {
            cout << b->data;    // 输出根结点的值
            if(b->lchild != nullptr || b->rchild != nullptr)
            {
                cout << "(";    // 有孩子结点时输出"("
                DispBTree(b->lchild);   // 递归输出左子树
                if(b->rchild != nullptr)
                    cout << ",";    // 有右孩子结点时输出","
                DispBTree(b->rchild);   // 递归输出右子树
                cout << ")";        // 输出")"
            }
        }
    }
public:
    // 查找值为x的结点
    BTNode* FindNode(char x)
    {
        return FindNode(r,x);
    }
private:
    BTNode* FindNode(BTNode* b, char x)  // 被FindNode函数调用
    {
        BTNode* p;
        if(b == nullptr)    // b为空时返回nullptr
            return nullptr;
        else if(b->data == x)    // b指向的结点值为x时，返回b
            return b;
        else
        {
            p = FindNode(b->lchild,x);  // 在左子树中查找
            if(p != nullptr)
                return p;   // 在左子树中找到p结点，则返回p
            else
                return FindNode(b->lchild,x);   // 否则在右子树中查找x
        }
    }
public:
    // 求二叉树高度
    int Height()
    {
        return Height(r);
    }
private:
    int Height(BTNode* b)
    {
        if(b == nullptr)
            return 0;   // 空树的高度为0
        else
            return max(Height(b->lchild), Height(b->rchild)) + 1;
    }

private:
    // 释放所有的结点的空间
    void DestroyBTree(BTNode* b)
    {
        if(b != nullptr)
        {
            DestroyBTree(b->lchild);    // 递归释放左子树
            DestroyBTree(b->rchild);    // 递归释放右子树
            delete b;                       // 释放根结点
        }
    }
};
